package Lee_code;

public class Lee_684 {

    private int n;
    int[] father;

    public Lee_684(){
        n = 1005;
        father = new int[n];

        //初始化
        for(int i = 0; i < n; i++){
            father[i] = i;
        }
    }
    public int find(int u){
        if(u == father[u]){
            return u;
        }
        father[u] = find(father[u]);
        return father[u];
    }
    private void join(int u, int v){
        u = find(u);
        v = find(v);
        if(u == v)
            return;
        father[v] = u;
    }

    private Boolean same(int u, int v){
        u = find(u);
        v = find(v);
        return u == v;
    }

    public int[] findRedundantConnection(int[][] edges)
    {
        for(int i = 0; i < edges.length; i++){
            if (same(edges[i][0], edges[i][1]))
            {
                return edges[i];
            }
            else {
                join(edges[i][0], edges[i][1]);
            }
        }
        return null;
    }
}
